package leetcode_jz_offer.day2_list;

/**
 * 定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
 **/
public class Num24_ReverseList {
    public ListNode reverseList(ListNode head) {
//        //1.创建新链表,遍历放入
//        //边遍历原链表,边头插插入新链表
//        //1->2->3->4->5尾插
//        //5->4->3->2->1头插
//        if(head==null||head.next==null){
//            return head;
//        }
//        ListNode dummyHead=new ListNode(5001);//虚拟头节点
//        while (head!=null){
//            //建立新链表结点
//            ListNode node=new ListNode(head.val);
//            //头插
//            node.next=dummyHead.next;
//            dummyHead.next=node;
//            head=head.next;//原链表向后遍历
//        }
//        return dummyHead.next;

        //2.原地移动:原来链表的next不是指向后继而是指向前驱
        if(head==null||head.next==null){
            return head;
        }
        ListNode cur=head;//当前遍历的结点,初始是头节点
        ListNode prev=null;//当前节点的前驱
        //1-2-3-4-5//cur为null时prev恰好到达最后一个节点,也就是换好后的头节点
        while (cur!=null){
            ListNode temp=cur.next;//暂存cur的下一位
            cur.next=prev;//cur的next指向前驱而不指向后继
            prev=cur;//prev向后遍历一位
            cur=temp;//cur相后遍历一位
        }
        return prev;


//        //3.递归
//        if(head==null||head.next==null){
//            return head;//链表一个节点或者没有结点时返回
//        }
//        //保存原先待处理结点的下一个结点
//        ListNode next=head.next;
//        ListNode newHead = reverseList(head.next);//newHead一直是最后一个节点
//
//        next.next=head;//下一个结点的next指向当前结点
//        head.next=null;//当前节点的next断开
//        return newHead;

    }
}
